import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2023-11-12
 * Time:15:51
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9,4,1,2,0,6,5,3,10,7,8};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        //控制增量，由arr.length/2  /2   /2...
        for(int i = arr.length/2;i>0;i/=2) {
            //使用插入排序，但是数组不是加一，而是加间隔
            for(int j = i;j< arr.length;j++) {
                int start = arr[j];
                int k = j - i;//k就是直接插入排序中的数组中当前元素的前一个元素
                while (k >= 0 && start > arr[k]) {
                    arr[k + i] = arr[k];
                    k = k-i;
                }
                arr[k+i] = start;
            }
        }
    }
}
